package com.cuz.daileetcode.bat100;

import java.util.Arrays;

public class 最多载两人的船同时过河问题 {
    public static void main(String[] args) {
        int[] ints = {1, 1, 1, 3, 5, 5, 5, 8, 9, 10, 10};
        System.out.println(solution1(ints, 11));
        System.out.println(solution2(ints, 11));
//        System.out.println(lastLess(ints, 5));
//        System.out.println(firstBetter(ints, 5));
    }

    public static int solution1(int[] arr, int shipLoad) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        Arrays.sort(arr);
        //过锤子
        if (arr[arr.length - 1] > shipLoad) {
            return -1;
        }
        if (arr.length == 1) {
            return 1;
        }
        int thin = 0;
        int fat = arr.length - 1;
        int shipShouldUse = 0;
        while (thin <= fat) {
            if (fat == thin) {
                shipShouldUse++;
                return shipShouldUse;
            }
            if (arr[fat] + arr[thin] > shipLoad) {
                fat--;
                shipShouldUse++;
            } else {
                fat--;
                thin++;
                shipShouldUse++;
            }
        }
        return shipShouldUse;
    }

    private static int solution2(int[] arr, int shipLoad) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        Arrays.sort(arr);
        //过锤子
        if (arr[arr.length - 1] > shipLoad) {
            return -1;
        }
        if (arr.length == 1) {
            return 1;
        }
        int shouldUse = 0;
        int i = arr.length - 1;
        for (; i >= 0; i--) {
            if (arr[i] == shipLoad) {
                shouldUse++;
            } else {
                break;
            }
        }
        int len = arr.length;
        int lastLessHalf = lastLess(arr, shipLoad / 2, 0, i);
        int firstBetterHalf = firstBetter(arr, shipLoad / 2, lastLessHalf, i);
        //1,1,1,1 shipLoad=20 lastLessHalf=arr.len-1   return (len + 1) / 2;
        //6,6,6,6,6 shipLoad=20 lastLessHalf=-1  return len;

        if (lastLessHalf == len - 1 || firstBetterHalf == -1) {
            return (len + 1) / 2;
        }
        if (lastLessHalf == -1 || firstBetterHalf == 1) {
            return len;
        }
        // 1  2  3  4  5   5  5   5   6   7   8   9   10
        // 0  1  2  3  5   6  7   8   9   10  11  12  13
        //shipLoad=10
        //firstBetterHalf = 9
        //lastLessHalf=3
        int thinCount = lastLessHalf + 1;
        int fatCount = i + 1 - firstBetterHalf;
        int midCount = i + 1 - thinCount - fatCount;
        if (thinCount > fatCount) {
            //瘦子大于胖子
            //那么让胖子和瘦子一对对过河
            shouldUse += fatCount;
            //消耗掉瘦子个数
            thinCount -= fatCount;
            //刚好等于一半的 两两一对
            if (midCount % 2 == 0) {
                shouldUse += (midCount) / 2;
            } else {
                //奇数 消耗一个瘦子
                shouldUse += (midCount - 1) / 2;
                thinCount--;
                shouldUse += 1;
            }
            //剩余的瘦子两两一对 如果奇数单独一船
            shouldUse += (thinCount + 1) / 2;
        } else if (thinCount == fatCount) {
            //瘦子等于胖子 那么两两一对
            shouldUse += thinCount;
            //刚好等于的人
            shouldUse += (midCount + 1) / 2;
        } else {
            //胖子大于瘦子 胖子消耗完瘦子 剩余的单独一船
            shouldUse += fatCount;
            //刚好等于的人
            shouldUse += (midCount + 1) / 2;
        }
        return shouldUse;
    }

    private static int lastLess(int[] arr, int target, int left, int right) {
        left = left - 1;
        right = right + 1;
        while (left + 1 != right) {
            int mid = ((right - left) >> 1) + left;
            if (arr[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return arr[left] < target ? left : -1;
    }

    private static int firstBetter(int[] arr, int target, int left, int right) {
        left = left - 1;
        right = right + 1;
        while (left + 1 != right) {
            int mid = ((right - left) >> 1) + left;
            if (arr[mid] <= target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return arr[right] > target ? right : -1;
    }
}
